#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣84. 柱状图中最大的矩形
// 【难度】困难
// 【提交】2025 9 18 https://leetcode.cn/problems/largest-rectangle-in-histogram/submissions/663938813/
// 【标签】单调栈；数组
class Solution_LC0084 {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        heights.push_back(0);
        vector<int> st;
        st.reserve(n + 1);
        long long maxArea = 0;

        for (int i = 0; i <= n; ++i) {
            int h = heights[i];
            while (!st.empty() && h < heights[st.back()]) {
                int height = heights[st.back()];
                st.pop_back();
                int left = st.empty() ? -1 : st.back();
                long long width = (long long)(i - left - 1);
                long long area = (long long)height * width;
                if (area > maxArea)
                    maxArea = area;
            }
            st.push_back(i);
        }
        return (int)maxArea;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组 heights，表示柱状图中各个柱子的高度，每个柱子彼此相邻且宽度为1。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * 模型：单调栈（Monotonic Stack），用于高效找到左右边界。
 * 
 * 二、标准解法状态设计
 * 使用单调栈存储柱状图的索引，栈中索引对应的高度保持递增顺序。
 * 对于每个新高度，与栈顶元素比较，若较小则计算以栈顶高度为高的矩形面积并弹出栈顶，
 * 直到栈为空或栈顶高度不大于当前高度。
 * 
 * 三、你的实现思路
 * 使用单调栈方法，从左到右遍历柱状图高度，维护一个存储索引的栈，栈中索引对应的高度递增。
 * 在末尾添加一个高度为0的柱状图，确保所有柱状图都能被处理。
 * 对于每个高度，弹出所有比它高的柱状图索引，并计算矩形面积。
 * 
 * 四、逐行注释（带细节提醒）
 * heights.push_back(0); // 添加哨兵，确保所有柱状图都能被处理
 * vector<int> st;       // 使用vector模拟单调栈
 * st.reserve(n + 1);    // 预分配空间，提高性能
 * long long maxArea = 0; // 初始化最大面积
 * for (int i = 0; i <= n; ++i) { // 遍历所有柱状图（包括哨兵）
 *     int h = heights[i]; // 当前高度
 *     while (!st.empty() && h < heights[st.back()]) { // 当前高度小于栈顶高度
 *         int height = heights[st.back()]; // 获取栈顶高度
 *         st.pop_back(); // 弹出栈顶
 *         int left = st.empty() ? -1 : st.back(); // 左边界
 *         long long width = (long long)(i - left - 1); // 计算宽度
 *         long long area = (long long)height * width; // 计算面积
 *         if (area > maxArea) maxArea = area; // 更新最大面积
 *     }
 *     st.push_back(i); // 将当前索引入栈
 * }
 * 
 * 五、正确性证明
 * 单调栈维护了高度递增的柱状图索引。当遇到较低高度时，可以确定栈中所有高于当前高度的柱状图
 * 的右边界就是当前位置，左边界是栈中前一个元素（如果存在）。算法保证了每个元素只入栈和出栈一次，
 * 正确性由单调栈性质保证。
 * 
 * 六、复杂度
 * 时间：O(n)，每个元素最多入栈和出栈一次。
 * 空间：O(n)，最坏情况下栈存储所有元素。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 时间复杂度低，只需一次遍历；
 *   - 代码高效，能够处理大规模数据；
 *   - 使用哨兵技巧简化边界处理。
 * 缺点：
 *   - 栈操作可能对初学者不易理解；
 *   - 修改了输入数组（添加哨兵），虽然不是严格要求的；
 *   - 使用了long long防止溢出，增加了复杂度。
 * 
 * 八、改进建议
 * 1. 可以不修改输入数组，而是在循环中特殊处理；
 * 2. 使用更明确的变量名（如 stack 代替 st）来增强可读性；
 * 3. 对于教学场景，可以添加注释解释为什么需要添加哨兵；
 * 4. 可以使用标准库的stack类，代码更清晰。
 * 
 * 九、一句话总结
 * 单调栈是解决"柱状图中最大矩形"问题的经典方法，你的实现准确且高效，能够熟练运用这一技巧解决相关问题。
 */